# -*- coding:utf-8 -*-
"""
https://leetcode-cn.com/problems/ones-and-zeroes

在计算机界中，我们总是追求用有限的资源获取最大的收益。
现在，假设你分别支配着 m 个 0 和 n 个 1。
另外，还有一个仅包含 0 和 1 字符串的数组。
你的任务是使用给定的 m 个 0 和 n 个 1 ，
找到能拼出存在于数组中的字符串的最大数量。每个 0 和 1 至多被使用一次。

注意:
    给定 0 和 1 的数量都不会超过 100。
    给定字符串数组的长度不会超过 600。

示例 1:
输入: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
输出: 4
解释: 总共 4 个字符串可以通过 5 个 0 和 3 个 1 拼出，即 "10","0001","1","0" 。

示例 2:
输入: Array = {"10", "0", "1"}, m = 1, n = 1
输出: 2
解释: 你可以拼出 "10"，但之后就没有剩余数字了。更好的选择是拼出 "0" 和 "1" 。

"""


class Solution:
    def findMaxForm(self, strs: list, m: int, n: int) -> int:
        """
        提示：多维 0-1 背包问题，动态规划求解：
        将题目转换为多维 0-1 背包问题就是：
        你有两个背包，编号零的包只能装零，编号一的包只能装一，它们的容量分别为 m, n。
        现在有一些物品，均是由零和一组成，这些物品都存储在 strs 中，
        如何装才能使两个包加起来装的物品数量最多？

        令 dp[i][j] 表示编号零的包和编号一的包容量为 i，j 时能装的物品的最多数量。
        那么对于下一个物品 s，它由 s0 个零和 s1 个一组成，那么这个物品该不该装进背包里？

                    1 + dp[i - s0][j - s1]    if 装
        dp[i][j] =/
                  \
                   dp[i][j]                  if 不装

        合并可得状态转移方程：
        dp[i][j] = max(dp[i][j], 1 + dp[i - s0][j - s1])

        """
        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
        for s in strs:
            s0 = s.count('0')
            s1 = s.count('1')
            for i in range(m, s0 - 1, -1):
                for j in range(n, s1 - 1, -1):
                    dp[i][j] = max(dp[i][j], 1 + dp[i - s0][j - s1])
        return dp[m][n]


if __name__ == "__main__":
    f = Solution()
    strs = ["10", "0001", "111001", "1", "0"]
    m, n = 5, 3
    print(f.findMaxForm(strs, m, n))